[Leetcode单排] 排列系列（N46 N47 N784）

字数统计: 1.2k阅读时长: 5 min

 2019/07/25  Share

晚上注册了新LeetCode账号，正式开始了LeetCode的从零单排。

LeetCode刷题顺序初步先按照花花酱的题目分类来，现在还不习惯直接在网页上写，暂时先用IDE。万事开头难，先把第一个50题做完吧。

46. Permutations

https://leetcode.com/problems/permutations/

全排列算是比较基础的题了，想到的第一个词就是回溯。可以选择对数组中的元素进行重排序，也可以选择从数组中每次取一个值放到自己的临时List中，这也就是下面这两种方法。回溯需要注意的是如果操作的对象是可变的，在递归后需要把它变回来。当然如果在递归中传递的是新对象，则没这个必要了。

解法一

/**
 * 解法一：以数组中元素排序为准
 */
public List<List<Integer>> permute(int[] nums) {
    if (nums == null || nums.length == 0) {
        return new ArrayList<>();
    }
    List<List<Integer>> result = new ArrayList<>();
    permute(nums, 0, result);
    return result;
}

private void permute(int[] nums, int i, List<List<Integer>> result) {
    if (nums.length == i) {
        List<Integer> cur = new ArrayList<>();
        for (Integer integer : nums) {
            cur.add(integer);
        }
        result.add(cur);
        return;
    }
    for (int j = i; j < nums.length; j++) {
        swap(nums, i, j);
        permute(nums, i + 1, result);
        swap(nums, i, j);
    }
}

private void swap(int[] nums, int m, int n) {
    int temp = nums[m];
    nums[m] = nums[n];
    nums[n] = temp;
}

解法二

/**
 * 解法二：以自定义List存放当前变量
 */
public List<List<Integer>> permute2(int[] nums) {
    if (nums == null || nums.length == 0) {
        return new ArrayList<>();
    }
    List<List<Integer>> result = new ArrayList<>();
    permute2(nums, new ArrayList<>(), result);
    return result;
}

/** 
 * 查看是否包含某元素，除了直接使用contains判断外，很多人使用了boolean[] visited，
 * 递归前visited[i] = true，递归后还需visited[i] = false;
 * https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
 */
private void permute2(int[] nums, List<Integer> cur, List<List<Integer>> result) {
    if (nums.length == cur.size()) {
        result.add(new ArrayList<>(cur));
        return;
    }
    for (int i : nums) {
        if (cur.contains(i)) {
            continue;
        }
        cur.add(i);
        permute2(nums, cur, result);
        cur.remove(cur.size() - 1);
    }
}

47. Permutations II

https://leetcode.com/problems/permutations-ii/

若数组中有重复元素，在全排列基础上要去除重复的结果。这个题目的解法不容易立即想到的，需要在全排列的树上完成剪枝的操作，而难点就在于判断树的哪颗节点该剪。

首先需要对整个数组进行排列，这是判断剪枝的前提。如果数组下标为i的元素的值与i-1元素的值相同，并且i-1元素并没有被访问过，那么下标为i的元素才可以被剪枝。其实难点在于理解前一个元素并没有被访问过，可以通过画图进行理解。

public List<List<Integer>> permuteUnique(int[] nums) {
    if (nums == null || nums.length == 0) {
        return new ArrayList<>();
    }
    // 排序
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    permute(nums, new ArrayList<>(), new boolean[nums.length], result);
    return result;
}

/**注意剪枝规则*/
private void permute(int[] nums, List<Integer> cur, boolean[] visit, List<List<Integer>> result) {
    if (cur.size() == nums.length) {
        result.add(new ArrayList<>(cur));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (visit[i]) {
            continue;
        }
        if (i > 0 && nums[i] == nums[i - 1] && !visit[i - 1]) {
            continue;
        }
        visit[i] = true;
        cur.add(nums[i]);
        permute(nums, cur, visit, result);
        cur.remove(cur.size() - 1);
        visit[i] = false;
    }
}

784. Letter Case Permutation

https://leetcode.com/problems/letter-case-permutation/

即输入一个String，里面的字符可以是数字、小写字母、大写字母。小写和大写可以相互转变，需要给出所有的 String 结果。答案也不难想，使用递归来做。

public List<String> letterCasePermutation(String S) {
    if (S == null || S.length() == 0) {
        return null;
    }
    List<String> result = new ArrayList<>();
    handle(S.toCharArray(), 0, result);
    return result;
}

private void handle(char[] chars, int i, List<String> result) {
    if (i == chars.length) {
        result.add(new String(chars));
        return;
    }
    if (Character.isDigit(chars[i])) {
        handle(chars, i + 1, result);
    } else {
        chars[i] = Character.toLowerCase(chars[i]);
        handle(chars, i + 1, result);
        chars[i] = Character.toUpperCase(chars[i]);
        handle(chars, i + 1, result);
    }

}

实际上第一遍做的时候，我是使用了一个 String 变量保存了当前结果，结果是对的，只是内存耗的稍多一点。当然这个变量是可以省的，只是需要更改字符数组。

private void handle(char[] chars, int i, String cur, List<String> result) {
    if (i == chars.length) {
        result.add(cur);
        return;
    }
    if (Character.isDigit(chars[i])) {
        handle(chars, i + 1, cur + chars[i], result);
    }
    if (Character.isLowerCase(chars[i])) {
        handle(chars, i + 1, cur + chars[i], result);
        handle(chars, i + 1, cur + Character.toUpperCase(chars[i]), result);
    }
    if (Character.isUpperCase(chars[i])) {
        handle(chars, i + 1, cur + chars[i], result);
        handle(chars, i + 1, cur + Character.toLowerCase(chars[i]), result);
    }
}

Next Post

[Leetcode单排] 组合系列 (N39 N40 N77 N216)
Previous Post

Clojure in Action: 概述、数据结构

CATALOG

1. 46. Permutations
1. 1.1. 解法一
2. 1.2. 解法二
2. 47. Permutations II
3. 784. Letter Case Permutation

